/**
 * 
 */
package calculation;

/**
 * @author Michael
 * Divide two integers without using multiplication, division and mod operator.
 */
public class DivideTwoIntegers {
	// O(quotient)?
	public static int divideByMinus(int dividend, int divisor) throws Exception {
		if (divisor == 0)
			throw new Exception("divisor cannot be zero!");

		long dividendL = dividend < 0 ? -dividend : dividend;
		long divisorL = divisor < 0 ? -divisor : divisor;
		long quotient = 0;

		while (dividendL >= divisorL) {
			dividendL -= divisorL;
			quotient++;
		}

		return (dividend ^ divisor) >> 31 == 1 ? -(int) quotient
				: (int) quotient;
	}

	// O(log(dividend)), used multiplication
	// does not work for Integer.MIN_VALUE if saving into int
	public static int divideByBinarySearch(int dividend, int divisor)
			throws Exception {
		if (divisor == 0)
			throw new Exception("divisor cannot be zero!");

		int sign = 1;
		if (dividend < 0) {
			dividend = -dividend;
			sign = -sign;
		}
		if (divisor < 0) {
			divisor = -divisor;
			sign = -sign;
		}

		// quotient range form 0 to dividend
		int low = 0;
		int high = dividend;
		int quotient = 0;
		while (low <= high) {
			quotient = low + ((high - low) >> 1);
			int remainder = dividend - quotient * divisor;
			if (remainder >= 0 && remainder < divisor) {
				return sign * quotient;
			} else if (remainder >= divisor) {
				low = quotient + 1;
			} else {
				high = quotient - 1;
			}
		}

		// should never reach here
		return Integer.MAX_VALUE;
	}

	// O(32c)
	public static int divideByBitOps(int dividend, int divisor)
			throws Exception {
		if (divisor == 0)
			throw new Exception("divisor cannot be zero!");

		boolean positive = true;
		if (dividend < 0) {
			dividend = -dividend;
			positive = !positive;
		}
		if (divisor < 0) {
			divisor = -divisor;
			positive = !positive;
		}

		int shift = 0;
		while ((divisor << shift) < dividend) {
			shift++;
		}

		int quotient = 0;
		while (dividend >= divisor) {
			if ((divisor << shift) <= dividend) {
				dividend -= (divisor << shift);
				quotient |= 1 << shift;
			}
			shift--;
		}

		return positive ? quotient : -quotient;
	}

	int divide(int dividend, int divisor) {
		boolean neg = false;
		if (dividend > 0 && divisor < 0 || dividend < 0 && divisor > 0)
			neg = true;
		int m = dividend, n = divisor, result = 0;
		dividend = Math.abs(dividend);
		divisor = Math.abs(divisor);
		while (dividend >= divisor) {
			int shift = 1;
			while (divisor << shift <= dividend)
				shift++;
			result += 1 << (shift - 1);
			dividend -= divisor << (shift - 1);
		}
		return neg ? -result : result;
	}

	public static int divideByBitOpsR(int dividend, int divisor) {
		if (dividend < divisor)
			return 0;
		if (dividend == divisor)
			return 0;

		int shift = 0;
		while ((divisor << shift) <= dividend) {
			shift++;
		}

		return divideByBitOpsR(dividend - (divisor << (shift - 1)), divisor) + 1 << (shift - 1);
	}

	public static int divideByBitWise(int dividend, int divisor) {

		if (divisor == 0) {
			// something is wrong
		}

		long dividendL = (dividend < 0) ? -(long) dividend : dividend;
		long divisorL = (divisor < 0) ? -(long) divisor : divisor;
		int quotient = 0;

		int shift = 0;
		while ((divisorL << shift) <= dividendL) {
			shift++;
		}

		for (int i = shift - 1; i >= 0; i--) {
			if (dividendL >= (divisorL << i)) {
				dividendL = dividendL - (divisorL << i);
				quotient = quotient + (1 << i);
			}
		}

		//		while (dividendL >= divisorL) {
		//			for (int i = 0; dividendL >= (divisorL << i); i++) {
		//				dividendL = dividendL - (divisorL << i);
		//				quotient = quotient + (1 << i);
		//			}
		//		}

		return (dividend ^ divisor) >>> 31 == 0 ? quotient : -quotient;
	}

	// best solution?
	// http://basicalgos.blogspot.com/2012/03/5-divide-two-integers.html

	/**
	 * 
	 */
	public DivideTwoIntegers() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 * @throws Exception 
	 */
	public static void main(String[] args) throws Exception {
		int dividend = -2147483648;
		int divisor = -3;
		System.out.printf("max integer is %d\n", Integer.MAX_VALUE);

		System.out.print(dividend + "/" + divisor + "=");
		System.out.println(divideByBitWise(dividend, divisor));

		// for (int i = 0; i < 100000; i++) {
		// int dividend = CreateUtils.randInt(100);
		// int divisor = CreateUtils.randInt(100);
		// try {
		// System.out.print(dividend + "/" + divisor + "=");
		// System.out.println(divideByMinus(dividend, divisor));
		// }
		// catch (Exception e) {
		// System.out.println("divisor is 0");
		// }
		// }
	}

}
